package linkedList;
/**
 * 
 * @Title: CandyLinkedList.java 
 * @Package linkedlist 
 * @Description: 自定义一个链表
 * 					1、设立虚拟头结点，将对头结点和后续结点的操作统一起来
 * 					2、add操作和remove操作都是根据索引完成的
 * @author CandyWall   
 * @date 2020年12月19日 下午7:32:32 
 * @version V1.0
 */
public class CandyLinkedList_v2<E> {
	private class Node {
		public E e;
		public Node next;
		
		public Node(E e, Node next) {
			this.e = e;
			this.next = next;
		}
		
		public Node(E e) {
			this(e, null);
		}

		public Node() {
			this(null, null);
		}

		@Override
		public String toString() {
			return e.toString();
		}
	}
	
	private Node dummyHead;
	private int size;
	
	public CandyLinkedList_v2() {
		//设立虚拟头结点
		dummyHead = new Node();
		size = 0;
	}

	/**
	 * 获取链表中的元素的个数
	 * @return
	 */
	public int getSize() {
		return size;
	}
	
	/**
	 * 返回链表是否为空
	 * @return
	 */
	public boolean isEmpty() {
		return size == 0;
	}
	
	/**
	 * 在索引为index处插入元素e
	 * @param e
	 * @param index
	 */
	public void add(int index, E e) {
		checkIndexRange(index);
		Node prev = dummyHead;
		
		for(int i = 0; i < index; i++)
			prev = prev.next;
		prev.next = new Node(e, prev.next);
		// 等价于
		/*Node node = new Node();
		node.next = prev.next;
		prev.next = node;*/
		size++;
	}
	
	/**
	 * 在链表头添加元素e
	 */
	public void addFirst(E e) {
		add(0, e);
	}
	
	/**
	 * 在链表尾添加元素e
	 * @param e
	 */
	public void addLast(E e) {
		add(size, e);
	}
	
	/**
	 * 获得链表的第index个位置的元素
	 * @param index
	 * @return
	 */
	public E get(int index) {
		checkIndexRange(index);
		
		Node cur = dummyHead.next;
		for(int i = 0; i < index; i++)
			cur = cur.next;
		return cur.e;
	}
	
	/**
	 * 获取链表的第一个元素
	 * @return
	 */
	public E getFirst() {
		return get(0);
	}
	
	/**
	 * 获取链表的最后一个元素
	 * @return
	 */
	public E getLast() {
		return get(size - 1);
	}
	
	/**
	 * 修改链表的第index个元素
	 * @param index
	 * @param e
	 */
	public void set(int index, E e) {
		checkIndexRange(index);
		
		Node cur = dummyHead.next;
		for(int i = 0; i < index; i++) {
			cur = cur.next;
		}
		cur.e = e;
	}
	
	/**
	 * 查找链表中是否有元素e
	 * @param e
	 * @return
	 */
	public boolean contains(E e) {
		/*for(Node cur = dummyHead.next; cur != null; cur = cur.next) {
			if(cur.e == e) {
				return true;
			}
		}*/
		Node cur = dummyHead.next;
		while(cur != null) {
			if(cur.e.equals(e))
				return true;
			cur = cur.next;
		}
		return false;
	}
	
	/**
	 * 从链表中删除第index个元素
	 * @param index
	 * @return
	 */
	public E remove(int index) {
		Node prev = dummyHead;
		for(int i = 0; i < index; i++)
			prev = prev.next;
		Node cur = prev.next;
		prev.next = cur.next;
		cur.next = null;
		size--;
		return cur.e;
	}
	
	/**
	 * 从链表中删除第一个元素
	 * @return
	 */
	public E removeFirst() {
		return remove(0);
	}
	
	/**
	 * 从链表中删除最后一个元素
	 * @return
	 */
	public E removeLast() {
		return remove(size - 1);
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder(String.format("CandyLinkedList: "));
		Node cur = dummyHead.next;
		while(cur != null) {
			sb.append(cur.e + "->");
			cur = cur.next;
		}
		sb.append("null");
		return sb.toString();
	}

	/**
	 * 判断索引范围是否合法
	 * @param index
	 */
	private void checkIndexRange(int index) {
		if(index < 0 || index > size)
			throw new IllegalArgumentException("index索引不合法");
	}
	
	public static void main(String[] args) {
		CandyLinkedList_v2<Integer> linkedList = new CandyLinkedList_v2<>();
		for(int i = 0; i < 4; i++) {
			linkedList.addLast(i);
			System.out.println(linkedList);
		}
		for(int i = 4; i < 10; i++) {
			linkedList.addFirst(i);
			System.out.println(linkedList);
		}
		linkedList.add(2, 666);
		System.out.println(linkedList);
		System.out.println(linkedList.remove(3));
		System.out.println(linkedList);
		System.out.println(linkedList.removeFirst());
		System.out.println(linkedList);
		System.out.println(linkedList.removeLast());
		System.out.println(linkedList);
	}
}
